package leetcode.sort;

import java.util.Arrays;
import java.util.Random;

public class 剑指_快排 {

    private static final Random random = new Random();

    public void quickSort(int[] data, int start, int end){
        if(data == null || start == end || data.length == 0) return;
        int index = partion(data, start, end);
        if(index > start){
            quickSort(data, start, index-1);
        }
        if(index < end){
            quickSort(data, index+1, end);
        }

    }

    /**
     * 随机选取一个值作为中间值 将小于该值的元素移到左边 大于的移到右边
     * @param data
     * @param start
     * @param end
     * @return 重新分配后中间值的位置
     */
    public int partion(int[] data, int start, int end){
        int flag = random.nextInt(end-start+1)+start; // 为了包含end所以+1
        int tmp = data[end];
        data[end] = data[flag];
        data[flag] = tmp;
        int small = start-1;
        for(int i = start; i <= end; i++){
            if(data[i] <= data[end]){
                small++;
                tmp = data[i];
                data[i] = data[small];
                data[small] = tmp;
            }
        }
        return small;
    }

    public static void main(String[] args){
        int[] a = new int[]{1};
        剑指_快排 s = new 剑指_快排();
        s.quickSort(a, 0, a.length-1);
        System.out.println(Arrays.toString(a));
    }

}
